"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional


class Solution:
    def __init__(self):
        self.clone_nodes = {}

    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        if not node:  # 空节点不克隆
            return None
        if node.val in self.clone_nodes:
            return self.clone_nodes[node.val]  # 克隆了的节点不重复克隆

        clone_node = Node(node.val)  # 创建一个克隆后的节点
        self.clone_nodes[node.val] = clone_node  # 存储克隆节点
        for neighbor in node.neighbors:
            # 克隆节点 克隆 被克隆节点的邻接列表
            clone_node.neighbors.append(self.cloneGraph(neighbor))
        return clone_node
